Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.
Example 1:
Input: data = [1,0,1,0,1] Output: 1 Explanation: There are 3 ways to group all 1's together: [1,1,1,0,0] using 1 swap. [0,1,1,1,0] using 2 swaps. [0,0,1,1,1] using 1 swap. The minimum is 1.
Example 2:
Input: data = [0,0,0,1,0] Output: 0 Explanation: Since there is only one 1 in the array, no swaps needed.
Example 3:
Input: data = [1,0,1,0,1,0,0,1,1,0,1] Output: 3 Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].
Example 4:
Input: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1] Output: 8
Constraints:
1 <= data.length <= 105data[i]is0or1.
Average Rating: 4.82 (22 votes)
Video Solution
Solution Article
Overview
Assuming that there are ones 1's in the input array data, we need to find a subarray, or a window, of length ones and put all 1's in it by swapping 0's out.
Therefore, among all windows of length ones, to find the minimum number of swaps required, we need to find the maximum number of 1's in the window so that we can make the smallest number of swaps to achieve the goal.
Figure 1. Find a subarray of length ones and swapping 0's with 1's.
Approach 1: Sliding Window with Two Pointers
Algorithm
We will use two pointers left and right to maintain a sliding window of length ones, and while we check every window through the input array data, we would calculate the number of 1's in it as cnt_one and store the largest one as max_one.
While the window is sliding through data, we want to maintain its length as ones.
At the same time, we also want to update the number of 1's in the window by adding the new boundary data[right] and deducting the left boundary data[left].
Complexity Analysis
- Time complexity: O(n), when n is the length of the array.
- Space complexity: O(1).
Approach 2: Sliding Window with Deque (Double-ended Queue)
Algorithm
An alternative way to implement the sliding window algorithm is to use Deque (Double-ended Queue).
The key idea is to maintain a deque deque with the size of ones by adding new elements to its right end and popping old elements from its left end.
More specifically speaking, after initializing deque, we would start appending elements to its right before its size reaches ones.
When there are ones elements in deque, we keep appending new elements to its right, and we would also remove the leftmost element from it so that its size is always ones.
Along this process, we can perform counting the number of 1's in this deque which is similar to Approach 1.
Complexity Analysis
- Time complexity: O(n), when n is the length of the array.
Note that the time complexities of adding the element to
deque's right end and popping the element from its left end are both O(1). - Space complexity: O(n), when n is the length of the array. This is because we need a Deque of size
ones.
I think the hints are unnecessarily cryptic because they are not complete sentences. They are written like Kevin from the Office when he tried to save time by omitting some words from a sentence.
December 1, 2020 10:02 AM
I really like the explanation in this article. Initially, I thought it would going to be tough. But it's more about the maths behind it.
Java, sliding window O(n) solution
class Solution {
public int minSwaps(int[] data) {
// `ones` will also serve as the size for our sliding window
int ones = Arrays.stream(data).sum();
int runningOnes = 0;
// Count 1s in first `ones` elements
for (int i = 0; i < ones; i++) {
runningOnes += data[i];
}
int swapsRequired = ones - runningOnes;
for (int i = ones; i < data.length; i++) {
// Drop leftmost from sliding window, and accumulate next right
runningOnes = runningOnes - data[i-ones] + data[I];
// runningOnes holds 1s seen in current window
swapsRequired = Math.min(swapsRequired, ones - runningOnes);
}
return swapsRequired;
}
}
April 15, 2021 1:22 PM
The solution 2 consumes more space but doesn't add benefits. It is useful just to show there are alternatives, but not good alternatives :-)
April 17, 2021 6:16 PM
One pointer only:
class Solution:
def minSwaps(self, data: List[int]) -> int:
window = data.count(1)
zeros, ans = 0, float('inf')
for i, d in enumerate(data):
if d == 0: zeros += 1
if i >= window - 1:
if i >= window and data[i - window] == 0:
zeros -= 1
ans = min(ans, zeros)
return ans
April 16, 2021 12:26 PM
Basically the idea is we want to create a window of however many ones there are in the array. We assume a certain substring contains all ones. If we assume everything to be ones within our sliding window (without actually changing the value) the number of swaps will be equal to the total number of 1s subtracted with the number of 1s inside our sliding window. We care about the ones outside our sliding window since those values will have to be swapped to zeros. The values that are alread zero outside the window do not matter. Its a unique case where we care about things outside our window instead of inside it. Don't let it trip you up.
public int minSwaps(int[] data) {
int totalOnes = 0, totalZeros = 0;
for (int i = 0; i < data.length; i++) {
if (data[i] == 1) totalOnes++;
else totalZeros++;
}
if (totalOnes == 1) return 0;
int right = totalOnes - 1, left = 0, min = Integer.MAX_VALUE, localOnes = 0, localZeros = 0;
for (int i = 0; i < totalOnes; i++) {
if (data[i] == 0) localZeros++;
else localOnes++;
}
while (right < data.length) {
int onesOutSideWindow = totalOnes - localOnes;
min = Math.min(onesOutSideWindow, min);
if (right + 1 >= data.length) break;
if (data[++right] == 0) localZeros++;
else localOnes++;
if (data[left++] == 1) localOnes--;
else localZeros--;
}
return min;
}
April 16, 2021 12:15 PM
What's the underlying math support here? The intuition is that the minimum swaps of each subarray window equals to the number of zeros. This is not always true. E.g. [1, 0, 0, 1, 1]. For the first subarray window "[1, 0, 0]", the minimum number of swaps is two as we have two 0s here. But it is actually one as we can swap "0, 0" with "1, 1" through one swap.
This is the prefix sum solution using the sliding window method.
int minSwaps(vector<int>& data) {
vector<int> pf(data.size());
partial_sum(data.begin(), data.end(), pf.begin());
pf.insert(pf.begin(), 0);
int ones = pf.back();
int j=ones; int i=0;
int max_ones=INT_MIN;
while (j<pf.size()){
max_ones=max(max_ones, pf[j]-pf[i]);
i++; j++;
}
return ones-max_ones;
}
February 7, 2021 8:54 PM
First count ones, fill a window of ones and swaps needed (zeros need to be swapped out) and then keep sliding window and compute minSwap:
class Solution {
public int minSwaps(int[] data) {
if (data == null || data.length < 2) return 0;
int ones = 0;
for (int i = 0; i < data.length; i++) {
if (data[i] == 1) ones++;
}
int swaps = 0;
for (int i = 0; i < ones; i++) {
if (data[i] == 0) swaps++;
}
int res = data.length-ones;
for (int i = ones; i < data.length; i++) {
res = Math.min(res, swaps);
if (data[i-ones] == 0) swaps--;
if (data[i] == 0) swaps++;
}
res = Math.min(res, swaps);
return res;
}
}
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int minSwaps(vector<int>& data) { }};
